home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / comm / mail / Mutt089src.lha / Mutt-0.89i-AMIGA / src / rx / rxanal.c < prev    next >
C/C++ Source or Header  |  1998-01-28  |  17KB  |  733 lines
  1. /*    Copyright (C) 1995, 1996 Tom Lord
  2.  * 
  3.  * This program is free software; you can redistribute it and/or modify
  4.  * it under the terms of the GNU Library General Public License as published by
  5.  * the Free Software Foundation; either version 2, or (at your option)
  6.  * any later version.
  7.  * 
  8.  * This program is distributed in the hope that it will be useful,
  9.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.  * GNU Library General Public License for more details.
  12.  * 
  13.  * You should have received a copy of the GNU Library General Public License
  14.  * along with this software; see the file COPYING.  If not, write to
  15.  * the Free Software Foundation, 59 Temple Place - Suite 330, 
  16.  * Boston, MA 02111-1307, USA. 
  17.  */
  18.  
  19.  
  20.  
  21. #include "rxall.h"
  22. #include "rxanal.h"
  23. #include "rxbitset.h"
  24. #include "rxsuper.h"
  25.  
  26.  
  27.  
  28.  
  29. #ifdef __STDC__
  30. int
  31. rx_posix_analyze_rexp (struct rexp_node *** subexps,
  32.                size_t * re_nsub,
  33.                struct rexp_node * node,
  34.                int id)
  35. #else
  36. int
  37. rx_posix_analyze_rexp (subexps, re_nsub, node, id)
  38.      struct rexp_node *** subexps;
  39.      size_t * re_nsub;
  40.      struct rexp_node * node;
  41.      int id;
  42. #endif
  43. {
  44.   if (node)
  45.     {
  46.       size_t this_subexp;
  47.       if (node->type == r_parens)
  48.     {
  49.       if (node->params.intval >= 0)
  50.         {
  51.           this_subexp = *re_nsub;
  52.           ++*re_nsub;
  53.           if (!*subexps)
  54.         *subexps = (struct rexp_node **)malloc (sizeof (struct rexp_node *) * *re_nsub);
  55.           else
  56.         *subexps = (struct rexp_node **)realloc (*subexps,
  57.                              sizeof (struct rexp_node *) * *re_nsub);
  58.         }
  59.     }
  60.       if (node->params.pair.left)
  61.     id = rx_posix_analyze_rexp (subexps, re_nsub, node->params.pair.left, id);
  62.       if (node->params.pair.right)
  63.     id = rx_posix_analyze_rexp (subexps, re_nsub, node->params.pair.right, id);
  64.       switch (node->type)
  65.     {
  66.     case r_cset:
  67.       node->len = 1;
  68.       node->observed = 0;
  69.       break;
  70.      case r_string:
  71.        node->len = node->params.cstr.len;
  72.        node->observed = 0;
  73.        break;
  74.     case r_cut:
  75.       node->len = 0;
  76.       node->observed = 0;
  77.       break;
  78.     case r_concat:
  79.     case r_alternate:
  80.       {
  81.         int lob, rob;
  82.         int llen, rlen;
  83.         lob = (!node->params.pair.left ? 0 : node->params.pair.left->observed);
  84.         rob = (!node->params.pair.right ? 0 : node->params.pair.right->observed);
  85.         llen = (!node->params.pair.left ? 0 : node->params.pair.left->len);
  86.         rlen = (!node->params.pair.right ? 0 : node->params.pair.right->len);
  87.         node->len = ((llen >= 0) && (rlen >= 0)
  88.              ? ((node->type == r_concat)
  89.                 ? llen + rlen
  90.                 : ((llen == rlen) ? llen : -1))
  91.              : -1);
  92.         node->observed = lob || rob;
  93.         break;
  94.       }
  95.     case r_opt:
  96.     case r_star:
  97.     case r_plus:
  98.       node->len = -1;
  99.       node->observed = (node->params.pair.left
  100.                 ? node->params.pair.left->observed
  101.                 : 0);
  102.       break;
  103.  
  104.     case  r_interval:
  105.       node->len = -1;
  106.       node->observed = 1;
  107.       break;
  108.  
  109.     case r_parens:
  110.       if (node->params.intval >= 0)
  111.         {
  112.           node->observed = 1;
  113.           (*subexps)[this_subexp] = node;
  114.         }
  115.       else
  116.         node->observed = (node->params.pair.left
  117.                   ? node->params.pair.left->observed
  118.                   : 0);
  119.       node->len = (node->params.pair.left
  120.                ? node->params.pair.left->len
  121.                : 0);
  122.       break;
  123.     case r_context:
  124.       switch (node->params.intval)
  125.         {
  126.         default:
  127.           node->observed = 1;
  128.           node->len = -1;
  129.           break;
  130.         case '^':
  131.         case '$':
  132.         case '=':
  133.         case '<':
  134.         case '>':
  135.         case 'b':
  136.         case 'B':
  137.         case '`':
  138.         case '\'':
  139.           node->observed = 1;
  140.           node->len = 0;
  141.           break;
  142.         }
  143.       break;
  144.     }
  145.       if (node->observed)
  146.     node->id = id++;
  147.       return id;
  148.     }
  149.   return id;
  150. }
  151.  
  152. /* Returns 0 unless the pattern can match the empty string. */
  153. #ifdef __STDC__
  154. int
  155. rx_fill_in_fastmap (int cset_size, unsigned char * map, struct rexp_node * exp)
  156. #else
  157. int
  158. rx_fill_in_fastmap (cset_size, map, exp)
  159.      int cset_size;
  160.      unsigned char * map;
  161.      struct rexp_node * exp;
  162. #endif
  163. {
  164.   if (!exp)
  165.     {
  166.     can_match_empty:
  167.       {
  168.     int x;
  169.     for (x = 0; x < cset_size; ++x)
  170.       map[x] = 1;
  171.       }
  172.       return 1;
  173.     }
  174.   
  175.   switch (exp->type)
  176.     {
  177.     case r_cset:
  178.       {
  179.     int x;
  180.     int most;
  181.     
  182.     most = exp->params.cset_size;
  183.     for (x = 0; x < most; ++x)
  184.       if (RX_bitset_member (exp->params.cset, x))
  185.         map[x] = 1;
  186.       }
  187.       return 0;
  188.  
  189.     case r_string:
  190.       if (exp->params.cstr.len)
  191.      {
  192.       map[exp->params.cstr.contents[0]] = 1;
  193.       return 0;
  194.      }
  195.       else
  196.     return 1;
  197.  
  198.     case r_cut:
  199.       return 1;
  200.       
  201.  
  202.     case r_concat:
  203.       return rx_fill_in_fastmap (cset_size, map, exp->params.pair.left);
  204.  
  205.       /* Why not the right branch?  If the left branch
  206.        * can't be empty it doesn't matter.  If it can, then
  207.        * the fastmap is already saturated, and again, the
  208.        * right branch doesn't matter.
  209.        */
  210.  
  211.  
  212.     case r_alternate:
  213.       return (  rx_fill_in_fastmap (cset_size, map, exp->params.pair.left)
  214.           | rx_fill_in_fastmap (cset_size, map, exp->params.pair.right));
  215.  
  216.     case r_parens:
  217.     case r_plus:
  218.       return rx_fill_in_fastmap (cset_size, map, exp->params.pair.left);
  219.  
  220.     case r_opt:
  221.     case r_star:
  222.       goto can_match_empty;
  223.       /* Why not the subtree?  These operators already saturate
  224.        * the fastmap. 
  225.        */
  226.  
  227.     case r_interval:
  228.       if (exp->params.intval == 0)
  229.     goto can_match_empty;
  230.       else
  231.     return rx_fill_in_fastmap (cset_size, map, exp->params.pair.left);
  232.       
  233.     case r_context:
  234.       goto can_match_empty;
  235.     }
  236.  
  237.   /* this should never happen but gcc seems to like it */
  238.   return 0;
  239.   
  240. }
  241.  
  242.  
  243. #ifdef __STDC__
  244. int
  245. rx_is_anchored_p (struct rexp_node * exp)
  246. #else
  247. int
  248. rx_is_anchored_p (exp)
  249.      struct rexp_node * exp;
  250. #endif
  251. {
  252.   if (!exp)
  253.     return 0;
  254.  
  255.   switch (exp->type)
  256.     {
  257.     case r_opt:
  258.     case r_star:
  259.     case r_cset:
  260.     case r_string:
  261.     case r_cut:
  262.       return 0;
  263.  
  264.     case r_parens:
  265.     case r_plus:
  266.     case r_concat:
  267.       return rx_is_anchored_p (exp->params.pair.left);
  268.  
  269.     case r_alternate:
  270.       return (   rx_is_anchored_p (exp->params.pair.left)
  271.           && rx_is_anchored_p (exp->params.pair.right));
  272.  
  273.  
  274.     case r_interval:
  275.       if (exp->params.intval == 0)
  276.     return 0;
  277.       else
  278.     return rx_is_anchored_p (exp->params.pair.left);
  279.       
  280.     case r_context:
  281.       return (exp->params.intval == '^');
  282.     }
  283.  
  284.   /* this should never happen but gcc seems to like it */
  285.   return 0;
  286. }
  287.  
  288.  
  289.  
  290. #ifdef __STDC__
  291. enum rx_answers
  292. rx_start_superstate (struct rx_classical_system * frame)
  293. #else
  294. enum rx_answers
  295. rx_start_superstate (frame)
  296.      struct rx_classical_system * frame;
  297. #endif
  298. {
  299.   struct rx_superset * start_contents;
  300.   struct rx_nfa_state_set * start_nfa_set;
  301.  
  302.   if (frame->rx->start_set)
  303.     start_contents = frame->rx->start_set;
  304.   else
  305.     {
  306.       {
  307.     struct rx_possible_future * futures;
  308.     futures = rx_state_possible_futures (frame->rx, frame->rx->start_nfa_states);
  309.  
  310.     if (!futures)
  311.       return rx_bogus;
  312.  
  313.     if (futures->next)
  314.       return rx_start_state_with_too_many_futures;
  315.  
  316.     start_nfa_set = futures->destset;
  317.       }
  318.       
  319.       start_contents =
  320.     rx_superstate_eclosure_union (frame->rx,
  321.                       rx_superset_cons (frame->rx, 0, 0),
  322.                       start_nfa_set);
  323.       
  324.       if (!start_contents)
  325.     return rx_bogus;
  326.         
  327.       start_contents->starts_for = frame->rx;
  328.       frame->rx->start_set = start_contents;
  329.     }
  330.  
  331.   if (   start_contents->superstate
  332.       && (start_contents->superstate->rx_id == frame->rx->rx_id))
  333.     {
  334.       if (frame->state)
  335.     {
  336.       rx_unlock_superstate (frame->rx, frame->state);
  337.     }
  338.       frame->state = start_contents->superstate;
  339.       /* The cached superstate may be in a semifree state.
  340.        * We need to lock it and preserve the invariant
  341.        * that a locked superstate is never semifree.
  342.        * So refresh it.
  343.        */
  344.       rx_refresh_this_superstate (frame->rx->cache, frame->state);
  345.       rx_lock_superstate (frame->rx, frame->state);
  346.       return rx_yes;
  347.     }
  348.   else
  349.     {
  350.       struct rx_superstate * state;
  351.  
  352.       rx_protect_superset (frame->rx, start_contents);
  353.       state = rx_superstate (frame->rx, start_contents);
  354.       rx_release_superset (frame->rx, start_contents);
  355.       if (!state)
  356.     return rx_bogus;
  357.       if (frame->state)
  358.     {
  359.       rx_unlock_